# LeetCode 105、从前序与中序遍历序列构造二叉树
# 一、题目描述
给定一棵树的前序遍历 preorder 与中序遍历 inorder。请构造二叉树并返回其根节点。
# 二、题目解析
# 三、参考代码
# 1、Java 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 从前序与中序遍历序列构造二叉树（ LeetCode 105 ）:https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
// 题目中说 preorder 和 inorder 均无重复元素
// 通过哈希表把中序遍历序列中的值和顺序建立映射关系
HashMap<Integer, Integer> map = new HashMap<>();
// 通过 for 循环，遍历完中序遍历序列中的所有元素
for (int i = 0; i < inorder.length; i++) {
// 以中序序列中的元素值 inorder[i] 作为 key
// 以位置 i 作为 value
// 存放到哈希表中
// 比如中序遍历序列中的元素是 [ A , D , E , F , G , H , M , Z ]
// 那么这个哈希表就是以下的样子
// | 索引 | 位置 |
// | A | 0 |
// | D | 1 |
// | E | 2 |
// | F | 3 |
// | G | 4 |
// | H | 5 |
// | M | 6 |
// | Z | 7 |
map.put(inorder[i], i);
}
// 下面开始构建二叉树
// 把前序遍历序列中的第一个元素 preorder[0] 作为二叉树的根节点
// 因为任意二叉树的前序遍历序列中的第一个元素，一定是二叉树的根节点
TreeNode root = new TreeNode(preorder[0]);
// 继续遍历前序遍历序列中的其它元素
for(int i = 1 ; i < preorder.length ; i++){
// 把当前遍历的元素构造为一个二叉树的节点
TreeNode node = new TreeNode(preorder[i]);
// 把构造的节点插入到以 root 为根节点的二叉树中
insertNode(root,node,map);
}
// 当 preorder 中所有元素都构造并且插入完毕之后
// 二叉树就完成了构建
return root;
}
// root : 二叉树的根节点
// node : 待插入的节点
// map : 节点值和中序遍历序列位置的映射
private void insertNode(TreeNode root,TreeNode node,HashMap<Integer,Integer> map){
// 当 root 和 node 指向的节点相同时，跳出循环
while(root != node){
// 如果 node 的中序遍历序列位置小于 root 的中序遍历序列位置
// 说明 node 应该在 root 的左子树中
if(map.get(node.val) < map.get(root.val)){
// 如果此时 root 没有左子树
if(root.left == null){
// 那么就把 node 设置为 root 的左子树
root.left = node;
}
// 1、如果之前 root 没有左子树，那么通过上面的代码，就设置好了 root 的左子树
// 也就是说 node 是 root 的一个叶子节点，完成了插入操作
// 把 root 指向 root.left 后，root 为 node，跳出了循环
// 2、如果之前 root 已经有左子树，那么就不能直接把 node 插入到 root 的左子树上
// 需要判断应该把 node 插入到 root 左子树上的孩子节点的那个位置上
// 比如现在的 root 是这个样子，node 为 A
// G
// /
// D
// / \
// ① ②
// root 已经有左子树 D 了，所以 node 应该考虑插入到 D 中的 ① 还是 ② 上面
// 所以，把 root 指向 root.left ，继续遍历 root 的左子树的情况
root = root.left;
}else{
// 如果 node 的中序遍历序列位置大于 root 的中序遍历序列位置
// 说明 node 应该在 root 的右子树中
// 如果此时 root 没有右子树
if(root.right == null){
// 那么就把 node 设置为 root 的右子树
root.right = node;
}
// 把 root 指向 root.right ，继续遍历 root 的右子树的情况
root = root.right;
}
}
}
}
# **2、**C++ 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 从前序与中序遍历序列构造二叉树（ LeetCode 105 ）:https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal
class Solution {
// 题目中说 preorder 和 inorder 均无重复元素
// 通过哈希表把中序遍历序列中的值和顺序建立映射关系
unordered_map<int, int> map;
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
// 通过 for 循环，遍历完中序遍历序列中的所有元素
for (int i = 0; i < inorder.size(); i++) {
// 以中序序列中的元素值 inorder[i] 作为 key
// 以位置 i 作为 value
// 存放到哈希表中
// 比如中序遍历序列中的元素是 [ A , D , E , F , G , H , M , Z ]
// 那么这个哈希表就是以下的样子
// | 索引 | 位置 |
// | A | 0 |
// | D | 1 |
// | E | 2 |
// | F | 3 |
// | G | 4 |
// | H | 5 |
// | M | 6 |
// | Z | 7 |
map[inorder[i]] = i;
}
// 下面开始构建二叉树
// 把前序遍历序列中的第一个元素 preorder[0] 作为二叉树的根节点
// 因为任意二叉树的前序遍历序列中的第一个元素，一定是二叉树的根节点
TreeNode *root = new TreeNode(preorder[0]);
// 继续遍历前序遍历序列中的其它元素
for(int i = 1 ; i < preorder.size() ; i++){
// 把当前遍历的元素构造为一个二叉树的节点
TreeNode *node = new TreeNode(preorder[i]);
// 把构造的节点插入到以 root 为根节点的二叉树中
insertNode(root,node);
}
// 当 preorder 中所有元素都构造并且插入完毕之后
// 二叉树就完成了构建
return root;
}
// root : 二叉树的根节点
// node : 待插入的节点
private:
void insertNode(TreeNode *root,TreeNode *node){
// 当 root 和 node 指向的节点相同时，跳出循环
while(root != node){
// 如果 node 的中序遍历序列位置小于 root 的中序遍历序列位置
// 说明 node 应该在 root 的左子树中
if(map[node->val] < map[root->val]){
// 如果此时 root 没有左子树
if(root->left == NULL){
// 那么就把 node 设置为 root 的左子树
root->left = node;
}
// 1、如果之前 root 没有左子树，那么通过上面的代码，就设置好了 root 的左子树
// 也就是说 node 是 root 的一个叶子节点，完成了插入操作
// 把 root 指向 root.left 后，root 为 node，跳出了循环
// 2、如果之前 root 已经有左子树，那么就不能直接把 node 插入到 root 的左子树上
// 需要判断应该把 node 插入到 root 左子树上的孩子节点的那个位置上
// 比如现在的 root 是这个样子，node 为 A
// G
// /
// D
// / \
// ① ②
// root 已经有左子树 D 了，所以 node 应该考虑插入到 D 中的 ① 还是 ② 上面
// 所以，把 root 指向 root.left ，继续遍历 root 的左子树的情况
root = root->left;
}else{
// 如果 node 的中序遍历序列位置大于 root 的中序遍历序列位置
// 说明 node 应该在 root 的右子树中
// 如果此时 root 没有右子树
if(root->right == NULL){
// 那么就把 node 设置为 root 的右子树
root->right = node;
}
// 把 root 指向 root.right ，继续遍历 root 的右子树的情况
root = root->right;
}
}
}
};
# 3、Python 代码
#登录 AlgoMooc 官网获取更多算法图解
# https://www.algomooc.com
# 作者：程序员吴师兄
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# 从前序与中序遍历序列构造二叉树（ LeetCode 105 ）:https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
# 题目中说 preorder 和 inorder 均无重复元素
# 通过哈希表把中序遍历序列中的值和顺序建立映射关系
# 通过 for 循环，遍历完中序遍历序列中的所有元素
map = dict()
for i in range(len(inorder)) :
# 以中序序列中的元素值 inorder[i] 作为 key
# 以位置 i 作为 value
# 存放到哈希表中
# 比如中序遍历序列中的元素是 [ A , D , E , F , G , H , M , Z ]
# 那么这个哈希表就是以下的样子
# | 索引 | 位置 |
# | A | 0 |
# | D | 1 |
# | E | 2 |
# | F | 3 |
# | G | 4 |
# | H | 5 |
# | M | 6 |
# | Z | 7 |
map[inorder[i]] = i
# 下面开始构建二叉树
# 把前序遍历序列中的第一个元素 preorder[0] 作为二叉树的根节点
# 因为任意二叉树的前序遍历序列中的第一个元素，一定是二叉树的根节点
root = TreeNode(preorder[0])
# 继续遍历前序遍历序列中的其它元素
for i in range( 1 ,len(preorder)):
# 把当前遍历的元素构造为一个二叉树的节点
node = TreeNode(preorder[i])
# 把构造的节点插入到以 root 为根节点的二叉树中
self.insertNode(root,node,map)
# 当 preorder 中所有元素都构造并且插入完毕之后
# 二叉树就完成了构建
return root
# root : 二叉树的根节点
# node : 待插入的节点
def insertNode(self , root : TreeNode, node : TreeNode,map:dict) :
# 当 root 和 node 指向的节点相同时，跳出循环
while root != node :
# 如果 node 的中序遍历序列位置小于 root 的中序遍历序列位置
# 说明 node 应该在 root 的左子树中
if map[node.val] < map[root.val] :
# 如果此时 root 没有左子树
if not root.left :
# 那么就把 node 设置为 root 的左子树
root.left = node
# 1、如果之前 root 没有左子树，那么通过上面的代码，就设置好了 root 的左子树
# 也就是说 node 是 root 的一个叶子节点，完成了插入操作
# 把 root 指向 root.left 后，root 为 node，跳出了循环
# 2、如果之前 root 已经有左子树，那么就不能直接把 node 插入到 root 的左子树上
# 需要判断应该把 node 插入到 root 左子树上的孩子节点的那个位置上
# 比如现在的 root 是这个样子，node 为 A
# G
# /
# D
# / \
# ① ②
# root 已经有左子树 D 了，所以 node 应该考虑插入到 D 中的 ① 还是 ② 上面
# 所以，把 root 指向 root.left ，继续遍历 root 的左子树的情况
root = root.left
else:
# 如果 node 的中序遍历序列位置大于 root 的中序遍历序列位置
# 说明 node 应该在 root 的右子树中
# 如果此时 root 没有右子树
if not root.right :
# 那么就把 node 设置为 root 的右子树
root.right = node
# 把 root 指向 root.right ，继续遍历 root 的右子树的情况
root = root.right